package lib.checkrep;

public abstract class AdjacencyMapCheck {

  /**
   * Returns true if map is connected
   * if map[i][j] is in impassable it means that no road are between them
   * @map must be square
   */
  public static boolean Connected(String[] map, String impassable) {
    assert ArrayStringCheck.ElementsLengthInRange(map, map.length, map.length);

    boolean[][] ok = new boolean[map.length][map.length];
    for (int i = 0; i < map.length; ++i) for (int j = 0; j < map.length; ++j) {
      if (impassable.contains(String.valueOf(map[i].charAt(j)))) {
        ok[i][j] = false;
      } else {
        ok[i][j] = true;
      }
    }

    // Floyd warshall
    for (int i = 0; i < map.length; ++i)
      for (int j = 0; j < map.length; ++j)
        for (int k = 0; k < map.length; ++k)
          ok[j][k] |= (ok[j][i] && ok[i][k]);

    for (int i = 0; i < map.length; ++i) {
      for (int j = 0; j < map.length; ++j) {
        if (i == j) continue;
        if (!ok[i][j]) return false;
      }
    }

    return true;

  }
}
